package com.mid;

/**
 * Created by Lxk on 2020/2/29.
 */
public class Solution279 {

    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = i;
            for (int k = 1; k <= Math.sqrt(i); k++) {
                //遍历每个完全平方数，通过已有方案，来寻找已知的最小方案
                dp[i] = Math.min(dp[i], dp[i - k * k] + 1);
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        Solution279 solution279 = new Solution279();
        System.out.println(solution279.numSquares(12));
    }

}
